#include <iostream>
#include <vector>
using namespace std;

#if 0
int divisor[3] = {2, 3, 5};
bool IsUgly(int k) {
	for (unsigned int d = 0; d < sizeof(divisor)/sizeof(divisor[0]); ++d) {
		while(k % divisor[d] == 0)
			k /= divisor[d];
	}
	return k == 1 ? true : false;
}
int FindNthUglyNum(int index) {
	int k = 0;
	int cnt = 0;
	while(cnt < index){
		k++;
		if (IsUgly(k)) {
			cnt++;
		}
	}
	return k;
}
#else 

int min(int m1, int m2, int m3) {
	return  min<int>(min<int>(m1, m2), m3);
}

int FindNthUglyNum(int index) {
	vector<int> UglyArray;
	UglyArray.push_back(1);

	int idx2 = 0, idx3 = 0, idx5 = 0;
	int m, m2, m3, m5;

	while(--index) {
		m2 = 2 * UglyArray[idx2];
		m3 = 3 * UglyArray[idx3];
		m5 = 5 * UglyArray[idx5];
		m = min(m2, m3, m5);
		UglyArray.push_back(m);
		if (m2 <= m)
			idx2++;
		if (m3 <= m)
			idx3++;
		if (m5 <= m)
			idx5++;
	}
	return UglyArray.back();
}



#endif

int main() {

	int n;
	cout << "Input the nth ugly number you want: ";
	cin >> n;
	cout << "Ugly number at " << n << "th is: " 
		 << FindNthUglyNum(n)
		 << endl;
	
	return 0;
}
